#ifndef __CSHASHMAP_H__
#define __CSHASHMAP_H__
#include <new>

template<class K>
class CSHashMapKeyOperation
{
public:
	static void Construct(K* to,K* from)
	{
		new(to) K(*from);
	}

	static void Destruct(K* k)
	{
		k->~K();
	}
};

template<class V>
class CSHashMapValueOperation
{
public:
	static void Construct(V* to,V* from)
	{
		new(to) V(*from);
	}

	static void Destruct(V* v)
	{
		v->~V();
	}
};

template<class K,int MapSize>
class HashCode
{
public:
	static int Get(K& key)
	{
		static unsigned int Mask = MapSize-1;
		int tmp = (int)key;
		int ret=0;
		while(tmp!=0)
		{
			ret+=tmp&Mask;
			tmp/=MapSize;
		}
		ret=ret&Mask;
		return ret;
	}
	static bool Cmp(K& k1,K& k2)
	{
		return k1==k2;
	}
};

struct SHashMapHead
{
	SHashMapHead* NextHash;
	SHashMapHead** PrecHash;
	SHashMapHead* Next;
	SHashMapHead* Prec;
};

template<class K,class V>
struct SHashMapData
{
	K first;
	V second;
};


template<class K,class V,class Mem,int MapSize>
class CSHashMapBase
{
	typedef CSHashMapKeyOperation<K> KOp;
	typedef CSHashMapValueOperation<V> VOp;
	typedef HashCode<K,MapSize> HC;
public:
	class iterator
	{
	public:
		iterator() {mHead=0;}
		explicit iterator(SHashMapHead* head) {mHead=head;}
		iterator(const iterator& iter) {mHead=iter.mHead;}
		iterator& operator=(const iterator& iter) {mHead=iter.mHead;return *this;}
		iterator& operator++() {mHead=mHead->Next;return *this;}
		iterator& operator--() {mHead=mHead->Prec;return *this;}
		bool operator==(const iterator& iter) {return mHead==iter.mHead;}
		bool operator!=(const iterator& iter) {return mHead!=iter.mHead;}
		SHashMapData<K,V>& operator*() {return *((SHashMapData<K,V>*)(mHead+1));}
		SHashMapData<K,V>* operator->() {return (SHashMapData<K,V>*)(mHead+1);}
	public:
		SHashMapHead* mHead;
	};
public:
	CSHashMapBase() {Init();}
	~CSHashMapBase() {Clear();}

	SHashMapHead* Malloc()
	{
		return (SHashMapHead*)Mem::Malloc(sizeof(SHashMapHead)+sizeof(SHashMapData<K,V>));
	}
	void Free(SHashMapHead* head)
	{
		Mem::Free((void*)head);
	}
	void Init()
	{
		for(int i=0;i<MapSize;++i)
		{
			mMap[i]=0;
		}
		mNum=0;
		mHead.Next=&mHead;
		mHead.Prec=&mHead;
	}
	void Clear();

	iterator Begin() {return iterator(mHead.Next);}
	iterator End() {return iterator(&mHead);}

	iterator Insert(K& key,V& val);
	iterator Erase(iterator& iter);

	iterator Find(K& key);
	bool Found(K& key) {return Find(key)!=End();}
	V* FindPtr(K& key);
	V& FindRef(K& key);
	void Remove(K& key);
	V& operator[](K& key) {return FindRef(key);}

private:
	SHashMapHead mHead;
	SHashMapHead* mMap[MapSize];
	int mNum;
};

template<class K,class V,class Mem,int MapSize>
typename CSHashMapBase<K,V,Mem,MapSize>::iterator CSHashMapBase<K,V,Mem,MapSize>::Insert(K& key,V& val)
{
	iterator finditer = Find(key);
	if(finditer!=End())
		return End();

	SHashMapHead* head = Malloc();
	SHashMapData<K,V>* data = (SHashMapData<K,V>*)(head+1);
	KOp::Construct(&data->first,&key);
	VOp::Construct(&data->second,&val);

	head->Next=mHead.Prec->Next;
	head->Prec=mHead.Prec;
	mHead.Prec->Next=head;
	mHead.Prec=head;

	int hashval = HC::Get(key);
	if(mMap[hashval])
		mMap[hashval]->PrecHash=&(head->NextHash);
	head->NextHash=mMap[hashval];
	head->PrecHash=mMap+hashval;
	mMap[hashval]=head;
	mNum++;

	return iterator(head);
}

template<class K,class V,class Mem,int MapSize>
typename CSHashMapBase<K,V,Mem,MapSize>::iterator CSHashMapBase<K,V,Mem,MapSize>::Erase(typename CSHashMapBase<K,V,Mem,MapSize>::iterator& iter)
{
	if(iter==End())
		return End();
	SHashMapHead*& head = iter.mHead;
	iterator retiter(head->Next);

	*(head->PrecHash) = head->NextHash;
	if(head->NextHash)
		head->NextHash->PrecHash = head->PrecHash;
	head->Next->Prec=head->Prec;
	head->Prec->Next=head->Next;

	SHashMapData<K,V>* data = (SHashMapData<K,V>*)(head+1);
	KOp::Destruct(&data->first);
	VOp::Destruct(&data->second);
	Free(head);
	mNum--;
	return retiter;
}

template<class K,class V,class Mem,int MapSize>
typename CSHashMapBase<K,V,Mem,MapSize>::iterator CSHashMapBase<K,V,Mem,MapSize>::Find(K& key)
{
	int hashcode = HC::Get(key);
	for(SHashMapHead* Node = mMap[hashcode];Node!=0;Node=Node->NextHash)
	{
		SHashMapData<K,V>* Data = (SHashMapData<K,V>*)(Node+1);
		if(HC::Cmp(Data->first,key) )
			return iterator(Node);
	}
	return End();
}

template<class K,class V,class Mem,int MapSize>
V* CSHashMapBase<K,V,Mem,MapSize>::FindPtr(K& key)
{
	iterator iter = Find(key);
	if(iter==End())
		return 0;
	return &(iter->second);
}

template<class K,class V,class Mem,int MapSize>
V& CSHashMapBase<K,V,Mem,MapSize>::FindRef(K& key)
{
	iterator iter = Find(key);
	if(iter==End())
		return *((V*)0);
	return iter->second;
}

template<class K,class V,class Mem,int MapSize>
void CSHashMapBase<K,V,Mem,MapSize>::Remove(K& key)
{
	iterator iter = Find(key);
	if(iter==End())
		return ;
	Erase(iter);
}

template<class K,class V,class Mem,int MapSize>
void CSHashMapBase<K,V,Mem,MapSize>::Clear()
{
	for(iterator iter=Begin();iter!=End();)
	{
		iter=Erase(iter);
	}
}


#endif

